//将一个 二叉搜索树 就地转化为一个 已排序的双向循环链表 。 
//
// 对于双向循环列表，你可以将左右孩子指针作为双向循环链表的前驱和后继指针，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。 
//
// 特别地，我们希望可以 就地 完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中最小元素的指针。 
//
// 
//
// 示例 1： 
//
// 
//输入：root = [4,2,5,1,3] 
//
//
//输出：[1,2,3,4,5]
//
//解释：下图显示了转化后的二叉搜索树，实线表示后继关系，虚线表示前驱关系。
//
// 
//
// 示例 2： 
//
// 
//输入：root = [2,1,3]
//输出：[1,2,3]
// 
//
// 示例 3： 
//
// 
//输入：root = []
//输出：[]
//解释：输入是空树，所以输出也是空链表。
// 
//
// 示例 4： 
//
// 
//输入：root = [1]
//输出：[1]
// 
//
// 
//
// 提示： 
//
// 
// -1000 <= Node.val <= 1000 
// Node.left.val < Node.val < Node.right.val 
// Node.val 的所有值都是独一无二的 
// 0 <= Number of Nodes <= 2000 
// 
//
// 注意：本题与主站 426 题相同：https://leetcode-cn.com/problems/convert-binary-search-tree-
//to-sorted-doubly-linked-list/ 
//
// Related Topics 栈 树 深度优先搜索 二叉搜索树 链表 二叉树 双向链表 👍 758 👎 0


package LeetCode.editor.cn;


import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author ldltd
 * @date 2025-05-12 10:23:53
 * @description LCR 155.将二叉搜索树转化为排序的双向链表
 
 */
 
public class ErChaSouSuoShuYuShuangXiangLianBiaoLcof {
    public static void main(String[] args) {
    //测试代码
    ErChaSouSuoShuYuShuangXiangLianBiaoLcof fun = new ErChaSouSuoShuYuShuangXiangLianBiaoLcof();
    Solution solution= fun.new Solution();
    
    }

//leetcode submit region begin(Prohibit modification and deletion)

// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};

class Solution {
    //感觉应该就是把中序遍历设置成链表，末节点连接头节点，然后返回头节点
    //非迭代
    public Node treeToDoublyList1(Node root) {
        Deque<Tuple<Integer,Node>> st=new ArrayDeque<>();
        List<Node> res=new ArrayList<>();
        st.push(new Tuple<>(0,root));
        while (!st.isEmpty()){
            Tuple<Integer,Node> pop=st.pop();
            if (pop.second==null) continue;
            if(pop.first==0){
                st.push(new Tuple<>(0,pop.second.right));
                st.push(new Tuple<>(1,pop.second));
                st.push(new Tuple<>(0,pop.second.left));
            }else {
                res.add(pop.second);
            }
        }
        if (res.isEmpty()) return null;
        Node p=res.get(0);
        Node head=p;
        for (int i = 1; i < res.size(); i++) {
            Node cur=res.get(i);
            p.right=cur;
            cur.left=p;
            p=cur;
        }
        p.right=head;
        head.left=p;
        return head;
    }
    public class Tuple<T1, T2> {
        private T1 first;
        private T2 second;

        // 构造函数
        public Tuple(T1 first, T2 second) {
            this.first = first;
            this.second = second;
        }

        // 获取第一个元素
        public T1 getFirst() {
            return first;
        }

        // 获取第二个元素
        public T2 getSecond() {
            return second;
        }

        // 设置第一个元素
        public void setFirst(T1 first) {
            this.first = first;
        }

        // 设置第二个元素
        public void setSecond(T2 second) {
            this.second = second;
        }

        @Override
        public String toString() {
            return "(" + first + ", " + second + ")";
        }

    }
    public Node treeToDoublyList(Node root){
       List<Node> res=new ArrayList<>();
       helper(root,res);
       if(res.size()==0) return root;
         Node p=res.get(0);
        Node head=p;
        for (int i = 1; i < res.size(); i++) {
            Node cur=res.get(i);
            p.right=cur;
            cur.left=p;
            p=cur;
        }
        p.right=head;
        head.left=p;
        return head;
    }
    //递归
    private void helper(Node root,List<Node> res){
        if(root==null) return;;
        if(root.left!=null){
            helper(root.left,res);
        }
        res.add(root);
        if(root.right!=null){
            helper(root.right,res);
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
